/*
 * Lincheck
 *
 * Copyright (C) 2019 - 2024 JetBrains s.r.o.
 *
 * This Source Code Form is subject to the terms of the
 * Mozilla Public License, v. 2.0. If a copy of the MPL was not distributed
 * with this file, You can obtain one at http://mozilla.org/MPL/2.0/.
 */

package org.jetbrains.kotlinx.lincheck.strategy.managed

import org.jetbrains.kotlinx.lincheck.primitiveOrIdentityHashCode
import org.jetbrains.kotlinx.lincheck.runner.ExecutionPart
import org.jetbrains.kotlinx.lincheck.strategy.managed.LoopDetector.CodeIdentity.RegularCodeLocationIdentity
import org.jetbrains.kotlinx.lincheck.trace.MethodCallTracePoint
import org.jetbrains.kotlinx.lincheck.trace.ObstructionFreedomViolationExecutionAbortTracePoint
import org.jetbrains.kotlinx.lincheck.trace.SpinCycleStartTracePoint
import org.jetbrains.kotlinx.lincheck.trace.SwitchEventTracePoint
import org.jetbrains.kotlinx.lincheck.trace.TracePoint
import org.jetbrains.lincheck.util.isInTraceDebuggerMode
import org.jetbrains.lincheck.trace.UNKNOWN_CODE_LOCATION_ID
import org.jetbrains.lincheck.datastructures.ManagedCTestConfiguration

/**
 * The LoopDetector class identifies loops, active locks, and live locks by monitoring the frequency of visits to the same code location.
 * It operates under a specific scenario constraint due to its reliance on cache information about loops,
 * determined by thread executions and switches, which is only reusable in a single scenario.
 *
 * The LoopDetector functions in two modes: default and replay mode.
 *
 * In the default mode:
 *
 * In the default mode, LoopDetector has two states.
 * When a spin cycle is not detected yet, LoopDetector ignores method parameters and read/write values and receivers,
 * operating only with switch points and code locations.
 * When a spin cycle is detected, LoopDetector requests the replay of the execution and starts tracking
 * the parameters, etc., to detect a spin cycle period properly, taking into account all changes during the spin cycle.
 * When we run into a spin cycle again, LoopDetector tries to find the period using [currentThreadCodeLocationsHistory].
 * Visited regular code locations are stored in [currentThreadCodeLocationsHistory] as [RegularCodeLocationIdentity].
 * Parameters etc. are converted to the integer representation using hashcode and stored in [currentThreadCodeLocationsHistory]
 * as [ValueRepresentationIdentity].
 * But sometimes it's not possible, for example, in case of using random. In that case, LoopDetector omits parameters,
 * read/written values, etc., and tries to find the period using only switch points code locations.
 * Once it's found (or not) LoopDetector requests one more replay to avoid side effects, made by this spin cycle.
 *
 * - The LoopDetector tracks code location executions (using [currentThreadCodeLocationsHistory]) performed by threads.
 * The history is stored for the current thread and is cleared during a thread switch.
 * - A map ([currentThreadCodeLocationVisitCountMap]) is maintained to track the number of times a thread visits a certain code location.
 * This map is also cleared during a thread switch.
 * - If a code location is visited more than a defined [hangingDetectionThreshold], it is considered as a spin cycle.
 * The LoopDetector then tries to identify the sequence of actions leading to the spin cycle.
 * Once identified, this sub-interleaving is stored for future avoidance.
 * - A history of executions and switches is maintained to record the sequence of actions and thread switches.
 * - A [loopTrackingCursor] tracks executions and thread switches to facilitate early thread switches.
 * - A counter for operation execution [totalExecutionsCount] across all threads is maintained.
 * This counter increments with each code location visit and is increased by the hangingDetectionThreshold if a spin cycle is detected early.
 * - If the counter exceeds the [org.jetbrains.lincheck.datastructures.ManagedCTestConfiguration.DEFAULT_LIVELOCK_EVENTS_THRESHOLD], a total deadlock is assumed.
 * Due to the relative small size of scenarios generated by Lincheck, such a high number of executions indicates a lack of progress in the system.
 *
 * In the replay mode:
 * - The number of allowable events to execute in each thread is determined using saved information from the last interleaving.
 * - For instance, if the [currentInterleavingHistory] is [0: 2], [1: 3], [0: 3], [1: 3], [0: 3], ..., [1: 3], [0: 3] and a deadlock is detected,
 * the cycle is identified as [1: 3], [0: 3].
 * This means 2 executions in thread 0 and 3 executions in both threads 1 and 0 will be allowed.
 * - Execution is halted after the last execution in thread 0 using [LincheckAnalysisAbortedError].
 * - The logic for tracking executions and switches in replay mode is implemented in [ReplayModeLoopDetectorHelper].
 *
 * Note: An example of this behavior is detailed in the comments of the code itself.
 */
internal class LoopDetector(
    private val hangingDetectionThreshold: Int
) {
    /**
     * Current mode.
     */
    private var mode: Mode = Mode.DEFAULT

    /**
     * Thread id of the current thread.
     */
    private var currentThreadId = -1

    /**
     * Tracks the count of total thread execution points handled by the loop detector.
     */
    private var totalExecutionsCount = 0

    /**
     * Current threshold for detecting possible livelock conditions during execution.
     * It is initialized with the [hangingDetectionThreshold] value
     * and can be adjusted dynamically to influence the sensitivity of the spin-loop detection logic.
     */
    private var currentHangingDetectionThreshold = hangingDetectionThreshold

    /**
     * Map, which helps us to determine how many times the current thread visits some code location.
     */
    private val currentThreadCodeLocationVisitCountMap = mutableMapOf<Int, Int>()

    /**
     * Is used to find a cycle period inside the exact thread execution if it has hung.
     */
    private val currentThreadCodeLocationsHistory = mutableListOf<CodeIdentity>()

    /**
     * Threads switches and executions history to store sequences lead to loops.
     */
    private val currentInterleavingHistory = ArrayList<InterleavingHistoryNode>()

    /**
     * Set of interleaving event sequences lead to loops. (A set of previously detected hangs)
     */
    private val interleavingsLeadToSpinLockSet = InterleavingSequenceTrackableSet()

    /**
     * Helps to determine does current interleaving equal to some saved interleaving leading to spin cycle or not.
     */
    private val loopTrackingCursor = interleavingsLeadToSpinLockSet.cursor

    /**
     * Delegate helper, active in replay (trace collection) mode.
     * It just tracks executions and switches and helps to halt execution or switch in case of spin-lock early.
     */
    private var replayModeLoopDetectorHelper: ReplayModeLoopDetectorHelper? = null

    /**
     * Indicates whether replay mode is currently enabled in the `LoopDetector`.
     */
    val replayModeEnabled: Boolean
        get() = replayModeLoopDetectorHelper != null

    /**
     * Indicates that we are in a spin cycle iteration now.
     */
    val replayModeCurrentlyInSpinCycle: Boolean get() =
        replayModeLoopDetectorHelper?.currentlyInSpinCycle ?: false

    /**
     * In replay mode, represents the period of spin-cycle if spin-cycle was entered.
     */
    private val replayModeCurrentCyclePeriod: Int
        get() = replayModeLoopDetectorHelper?.currentCyclePeriod ?: 0

    /**
     * Is called before each interleaving processing
     */
    fun reset() {
        currentThreadId = -1
        totalExecutionsCount = 0
        currentHangingDetectionThreshold = hangingDetectionThreshold
        currentThreadCodeLocationVisitCountMap.clear()
        currentThreadCodeLocationsHistory.clear()
        currentInterleavingHistory.clear()
        replayModeLoopDetectorHelper?.reset()
    }

    fun enableReplayMode(failDueToDeadlockInTheEnd: Boolean) {
        if (isInTraceDebuggerMode) return

        val contextSwitchesBeforeHalt = findMaxPrefixLengthWithNoCycleOnSuffix(currentInterleavingHistory)
            ?.let { it.executionsBeforeCycle + it.cyclePeriod }
            ?: currentInterleavingHistory.size
        val spinCycleInterleavingHistory = currentInterleavingHistory.take(contextSwitchesBeforeHalt)
        // Remove references to the interleaving tree
        interleavingsLeadToSpinLockSet.clear()
        loopTrackingCursor.clear()

        replayModeLoopDetectorHelper = ReplayModeLoopDetectorHelper(
            interleavingHistory = spinCycleInterleavingHistory,
            failDueToDeadlockInTheEnd = failDueToDeadlockInTheEnd
        )
    }

    /*
     * When replaying executions, it's important to repeat the same thread switches
     * recorded in the loop detector history during the last execution.
     * For example, suppose that interleaving say us to switch
     * from thread 1 to thread 2 at execution position 200.
     * But after execution 10, a spin cycle with period 2 occurred,
     * so we will switch from the spin cycle.
     * When we leave this cycle due to the switch for the first time,
     * interleaving execution counter may be near 200 and the strategy switch will happen soon.
     * But on the replay run, we will switch from thread 1 early, after 12 operations,
     * but no strategy switch will be performed for the next 200-12 operations.
     * This leads to the results of another execution, compared to the original failure results.
     * To avoid this bug when we're replaying some executions,
     * we have to follow only loop detector's history during the last execution.
     * In the considered example, we will retain that we will switch soon after
     * the spin cycle in thread 1, so no bug will appear.
     */
    fun shouldSwitch(): Boolean {
        return replayModeLoopDetectorHelper?.shouldSwitch() ?: false
    }

    /**
     * The `Decision` sealed class represents the different decisions
     * that can be made by the loop detector.
     */
    sealed class Decision {
        /**
         * This decision is returned when no livelock is detected,
         * and no further actions are required.
         */
        data object Idle : Decision()
        /**
         * This decision is returned when the execution has generated
         * a total number of events exceeding the predefined threshold.
         */
        data object EventsThresholdReached : Decision()

        /**
         * This decision is returned when the live-lock is detected and replay required to avoid potential side-effects.
         */
        data object LivelockReplayRequired : Decision()

        /**
         * This decision is returned when the live-lock is detected for the first time,
         * and we have to replay the execution analyzing method parameters additionally to
         * calculate the spin cycle period.
         */
        data object LivelockReplayToDetectCycleRequired : Decision()

        /**
         * This decision is returned when global live-lock is detected decisively,
         * and the execution has to be aborted with the failure.
         *
         * @property cyclePeriod The period of the spin-loop cycle.
         */
        data class LivelockFailureDetected(val cyclePeriod: Int) : Decision()

        /**
         * This decision is returned when a single thread enters a live-lock,
         * and a switch to other threads is required to see if they can unblock the execution.
         *
         * @property cyclePeriod The period of the spin-loop cycle.
         */
        data class LivelockThreadSwitch(val cyclePeriod: Int) : Decision()
    }

    /**
     * Updates the internal state of the loop detector to account for
     * the fact that thread [iThread] hits [codeLocation].
     *
     * The loop detector performs checks if the live-lock occurred,
     * and returns its decision.
     *
     * @see LoopDetector.Decision
     */
    fun visitCodeLocation(iThread: Int, codeLocation: Int): Decision {
        check(currentThreadId == iThread) {
            "The current thread id $currentThreadId is not equal to the one provided $iThread."
        }
        // Increase the total number of happened operations for live-lock detection
        totalExecutionsCount++
        // Ignore unknown code locations.
        if (codeLocation == UNKNOWN_CODE_LOCATION_ID) {
            return Decision.Idle
        }
        // Update code location visit counter
        updateCodeLocationVisitCounter(codeLocation)
        val count = currentThreadCodeLocationVisitCountMap.getOrDefault(codeLocation, 0)
        // If we are in replay mode, check if the replay has lead to a deadlock
        replayModeLoopDetectorHelper?.let {
            return it.detectLivelock()
        }
        // In trace debugger mode, check whether the count exceeds
        // the maximum number of repetitions for spin-loop detection.
        // Check whether the count exceeds the maximum number of repetitions for loop/hang detection.
        if (isInTraceDebuggerMode) {
            return when {
                // spin-loop detected - switch
                count > currentHangingDetectionThreshold ->
                    Decision.LivelockThreadSwitch(currentHangingDetectionThreshold)
                // live-lock detected - fail
                totalExecutionsCount > ManagedCTestConfiguration.DEFAULT_LIVELOCK_EVENTS_THRESHOLD ->
                    Decision.EventsThresholdReached
                // else - continue
                else -> Decision.Idle
            }
        }
        val detectedFirstTime = count > currentHangingDetectionThreshold
        val detectedEarly = loopTrackingCursor.isInCycle
        // detectedFirstTime and detectedEarly can both sometimes be true
        // when we can't find a cycle period and can't switch to another thread.
        if (detectedFirstTime && !detectedEarly) {
            if (mode == Mode.DEFAULT) {
                // Turn on parameters and read/write values and receivers tracking and request one more replay.
                mode = Mode.CYCLE_PERIOD_CALCULATION
                return Decision.LivelockReplayToDetectCycleRequired
            }
            registerCycle()
            // Turn off parameters tracking and request one more replay to avoid side effects.
            mode = Mode.DEFAULT
            // Enormous operations count considered as total spin lock
            if (totalExecutionsCount > ManagedCTestConfiguration.DEFAULT_LIVELOCK_EVENTS_THRESHOLD) {
                return Decision.EventsThresholdReached
            }
            // Replay current interleaving to avoid side effects caused by multiple cycle executions
            return Decision.LivelockReplayRequired
        }
        if (!detectedFirstTime && detectedEarly) {
            totalExecutionsCount += currentHangingDetectionThreshold
            val lastNode = currentInterleavingHistory.last()
            // spinCyclePeriod may be not 0 only we tried to switch
            // from the current thread but no available threads were available to switch
            if (lastNode.spinCyclePeriod == 0) {
                // transform current node to the state corresponding to early found cycle
                val cyclePeriod = loopTrackingCursor.cyclePeriod
                lastNode.executions -= cyclePeriod
                lastNode.spinCyclePeriod = cyclePeriod
                lastNode.executionHash = loopTrackingCursor.cycleLocationsHash
            }
            // Enormous operations count considered as total spin lock
            if (totalExecutionsCount > ManagedCTestConfiguration.DEFAULT_LIVELOCK_EVENTS_THRESHOLD) {
                return Decision.EventsThresholdReached
            }
        }
        if (detectedFirstTime || detectedEarly) {
            return Decision.LivelockThreadSwitch(replayModeCurrentCyclePeriod)
        }
        return Decision.Idle
    }

    /**
     * Updates the internal hit counters for a given code location during the execution process.
     * This method tracks the number of visits to a specific code location and appends it to the
     * current thread's code location history.
     *
     * @param codeLocation unique identifier of a code location being visited.
     * @return the updated number of times the specified code location has been visited by the current thread,
     *         or -1 if the `codeLocation` is unknown
     */
    private fun updateCodeLocationVisitCounter(codeLocation: Int) {
        require(codeLocation != UNKNOWN_CODE_LOCATION_ID)
        replayModeLoopDetectorHelper?.let {
            it.visitCodeLocation(codeLocation)
            return
        }
        val count = currentThreadCodeLocationVisitCountMap.getOrDefault(codeLocation, 0)
        currentThreadCodeLocationVisitCountMap[codeLocation] = count + 1
        if (mode != Mode.DEFAULT) {
            currentThreadCodeLocationsHistory += RegularCodeLocationIdentity(codeLocation)
        }
    }

    private fun updateInterleavingHistory(codeLocation: Int) {
        val lastInterleavingHistoryNode = currentInterleavingHistory.last()
        if (lastInterleavingHistoryNode.cycleOccurred) {
            return /* If we already ran into cycle and haven't switched than no need to track executions */
        }
        lastInterleavingHistoryNode.addExecution(codeLocation)
        loopTrackingCursor.onNextExecutionPoint()
    }

    /**
     * Called when we:
     * - Read/write some value.
     * - Use some object as a receiver (receiver is passed as a parameter [obj]).
     * - Use an index to access an array cell (index is passed as a parameter [obj]).
     *
     * Used only if LoopDetector is in the cycle calculation mode.
     * Otherwise, does nothing.
     */
    private fun passValue(obj: Any?) {
        if (mode == Mode.DEFAULT) return
        val hash = primitiveOrIdentityHashCode(obj)
        currentThreadCodeLocationsHistory += CodeIdentity.ValueRepresentationIdentity(hash)
    }

    /**
     * Called when we pass some parameters before method call in the instrumented call.
     * Used only if LoopDetector is in the cycle calculation mode.
     * Otherwise, does nothing.
     */
    private fun passParameters(params: Array<Any?>) {
        if (mode == Mode.DEFAULT) return
        params.forEach { param ->
            val hash = primitiveOrIdentityHashCode(param)
            currentThreadCodeLocationsHistory += CodeIdentity.ValueRepresentationIdentity(hash)
        }
    }

    /**
     * Called before regular method calls.
     */
    fun beforeMethodCall(codeLocation: Int, params: Array<Any?>) {
        passParameters(params)
        updateCodeLocationVisitCounter(codeLocation)
        updateInterleavingHistory(codeLocation)
    }

    /**
     * Called before atomic method calls.
     */
    @Suppress("UNUSED_PARAMETER")
    fun beforeAtomicMethodCall(codeLocation: Int, params: Array<Any?>) {
        // atomic methods are handled via `visitCodeLocation`,
        // so we only need to pass method parameters
        passParameters(params)
    }

    /**
     * Should be called before each read non-local mutable field read.
     */
    fun beforeReadField(receiver: Any?) {
        passValue(receiver)
    }

    /**
     * Should be called after each read non-local mutable field read.
     */
    fun afterRead(value: Any?) {
        passValue(value)
    }

    /**
     * Should be called before each non-local array element read.
     */
    fun beforeReadArrayElement(array: Any, index: Int) {
        passValue(array)
        passValue(index)
    }

    /**
     * Should be called before each read non-local field write.
     */
    fun beforeWriteField(receiver: Any?, value: Any?) {
        passValue(receiver)
        passValue(value)
    }

    /**
     * Should be called before each read non-local array element write.
     */
    fun beforeWriteArrayElement(array: Any, index: Int, value: Any?) {
        passValue(array)
        passValue(index)
        passValue(value)
    }

    fun onActorStart(iThread: Int) {
        check(iThread == currentThreadId)
        // if a thread has reached a new actor, then it means it has made some progress;
        // therefore, we reset the code location counters,
        // so that code location hits from a previous actor do not affect subsequent actors
        currentThreadCodeLocationVisitCountMap.clear()
    }

    /**
     * Is called before each interleaving part processing
     */
    fun beforePart(part: ExecutionPart, nextThread: Int) {
        if (currentThreadId == -1) {
            setFirstThread(nextThread)
        } else if (currentThreadId != nextThread) {
            beforeThreadSwitch(nextThread)
        }
        if (part == ExecutionPart.VALIDATION) {
            // Effectively disable spin-loop detection inside validation functions, because:
            // - during validation, there are no other threads to switch anyway;
            // - in our use cases of concurrent algorithms, many typical validation functions contain
            //   long-running for-loops iterating over large pre-allocated arrays,
            //   which size exceeds the default value of `hangingDetectionThreshold`.
            currentHangingDetectionThreshold = ManagedCTestConfiguration.DEFAULT_LIVELOCK_EVENTS_THRESHOLD + 1
        }
    }

    private fun setFirstThread(iThread: Int) {
        currentThreadId = iThread
        loopTrackingCursor.reset(iThread)
        currentInterleavingHistory.add(InterleavingHistoryNode(threadId = iThread))
    }

    fun onThreadFinish(iThread: Int) {
        check(iThread == currentThreadId)
        afterCodeLocation(codeLocation = UNKNOWN_CODE_LOCATION_ID)
    }

    /**
     * Called before a thread switch to another thread.
     */
    fun beforeThreadSwitch(nextThreadId: Int) {
        currentThreadId = nextThreadId
        currentThreadCodeLocationVisitCountMap.clear()
        currentThreadCodeLocationsHistory.clear()

        if (currentInterleavingHistory.isNotEmpty() &&
            currentInterleavingHistory.last().threadId == nextThreadId) {
            return
        }
        currentInterleavingHistory.add(
            InterleavingHistoryNode(
                threadId = nextThreadId,
                executions = 0,
            )
        )
        loopTrackingCursor.onNextSwitchPoint(nextThreadId)
        replayModeLoopDetectorHelper?.onNextSwitch()
    }

    /**
     * Is called after a thread switch back to a thread.
     */
    fun afterThreadSwitch(codeLocation: Int) {
        if (codeLocation == UNKNOWN_CODE_LOCATION_ID) return
        // After we switch back to the thread, no `visitCodeLocations` will be called
        // before the next switch point as it was called earlier.
        // But we need to track that this point is going to be executed after the switch,
        // so we pass it after the switch back,
        // but before the instruction is actually executed.
        updateCodeLocationVisitCounter(codeLocation)
    }

    fun afterCodeLocation(codeLocation: Int) {
        if (replayModeEnabled) return
        updateInterleavingHistory(codeLocation)
    }

    private fun registerCycle() {
        val (cycleInfo, switchPointsCodeLocationsHistory) = tryFindCycle()

        if (cycleInfo == null) {
            val lastNode = currentInterleavingHistory.last()
            val cycleStateLastNode = lastNode.asNodeCorrespondingToCycle(
                executionsBeforeCycle = switchPointsCodeLocationsHistory.size - 1,
                cyclePeriod = 0,
                cycleExecutionsHash = lastNode.executionHash // corresponds to a cycle
            )

            currentInterleavingHistory[currentInterleavingHistory.lastIndex] = cycleStateLastNode
            interleavingsLeadToSpinLockSet.addBranch(currentInterleavingHistory)
            return
        }
        /*
         * For nodes, correspond to cycles we re-calculate hash using only code locations related to the cycle,
         * because if we run into a deadlock, it's enough to show events before the cycle
         * and first cycle iteration in the current thread.
         */
        var cycleExecutionLocationsHash = switchPointsCodeLocationsHistory[cycleInfo.executionsBeforeCycle]
        for (i in cycleInfo.executionsBeforeCycle + 1 until cycleInfo.executionsBeforeCycle + cycleInfo.cyclePeriod) {
            cycleExecutionLocationsHash = cycleExecutionLocationsHash xor switchPointsCodeLocationsHistory[i]
        }

        val cycleStateLastNode = currentInterleavingHistory.last().asNodeCorrespondingToCycle(
            cyclePeriod = cycleInfo.cyclePeriod,
            cycleExecutionsHash = cycleExecutionLocationsHash, // corresponds to a cycle
            executionsBeforeCycle = cycleInfo.executionsBeforeCycle,
        )

        currentInterleavingHistory[currentInterleavingHistory.lastIndex] = cycleStateLastNode
        interleavingsLeadToSpinLockSet.addBranch(currentInterleavingHistory)
    }

    /**
     * Tries to find a spin cycle in [currentThreadCodeLocationsHistory] taking parameters
     * and values into account, or, if it's not possible, without it, using just switch points code locations.
     *
     * @return a pair of a [CycleInfo], corresponding to the spin cycle in a code locations history
     * **without** parameters and values, (i.e. considering only code locations) and a list of visited code
     * locations **without** parameters and values, only potential switch points.
     */
    private fun tryFindCycle(): Pair<CycleInfo?, List<Int>> {
        // Get the code locations history of potential switch points, without parameters and values.
        val historyWithoutParams = currentThreadCodeLocationsHistory.mapNotNull {
            (it as? RegularCodeLocationIdentity)?.location
        }
        // Trying to find a cycle with them.
        val cycleInfo = findMaxPrefixLengthWithNoCycleOnSuffix(currentThreadCodeLocationsHistory)
        // If it's not possible - searching for the cycle in the filtered history list - without params and values.
        if (cycleInfo == null) {
            return findMaxPrefixLengthWithNoCycleOnSuffix(historyWithoutParams) to historyWithoutParams
        }

        // If we found a spin cycle in the code locations history with parameters and values -
        // then we need to calculate how many executions,
        // that are potential switch points, before and during the cycle happened.
        // We need it because in normal mode LoopDetector only uses potential switch points code locations
        // to detect spin locks, so we have to count code locations that don't represent parameters or values.
        var cyclePeriod = 0
        var operationsBefore = 0

        var i = 0
        // Count how many potential switch point executions happened before the spin cycle.
        repeat(cycleInfo.executionsBeforeCycle) {
            // Potential switch point code locations are only RegularCodeLocationIdentity
            if (currentThreadCodeLocationsHistory[i] is RegularCodeLocationIdentity) {
                operationsBefore++
            }
            i++
        }
        repeat(cycleInfo.cyclePeriod) {
            // Potential switch point code locations are only RegularCodeLocationIdentity
            if (currentThreadCodeLocationsHistory[i] is RegularCodeLocationIdentity) {
                cyclePeriod++
            }
            i++
        }

        return CycleInfo(operationsBefore, cyclePeriod) to historyWithoutParams
    }

    /**
     * Prints the interleaving sequences tree set.
     * Utility function to debug spin-locks related internals.
     */
    @Suppress("unused")
    internal fun treeToString() = interleavingsLeadToSpinLockSet.treeToString()

    private enum class Mode {

        /**
         * The default mode of [LoopDetector]: analyzing only potential switch points code locations
         * and method enters/exits.
         */
        DEFAULT,

        /**
         * In this mode [LoopDetector] also takes into account parameters,
         * receivers and written/wrote values to calculate the spin cycle period properly.
         * After spin cycle is found, [DEFAULT] mode is enabled.
         */
        CYCLE_PERIOD_CALCULATION
    }

    /**
     * Represents either a regular code location [RegularCodeLocationIdentity], determined by [org.jetbrains.lincheck.descriptors.CodeLocations], or
     * a value [ValueRepresentationIdentity] (i.e. parameter, receiver written/read value) hashcode.
     */
    private sealed interface CodeIdentity {
        data class RegularCodeLocationIdentity(val location: Int): CodeIdentity
        data class ValueRepresentationIdentity(val identity: Int) : CodeIdentity
    }
}

internal val LoopDetector.Decision.isLivelockDetected get() = when (this) {
    is LoopDetector.Decision.LivelockThreadSwitch,
    is LoopDetector.Decision.LivelockReplayRequired,
    is LoopDetector.Decision.LivelockFailureDetected -> true

    else -> false
}

internal val LoopDetector.Decision.isReplayRequired get() = when (this) {
    is LoopDetector.Decision.LivelockReplayRequired,
    is LoopDetector.Decision.LivelockReplayToDetectCycleRequired -> true

    else -> false
}

/**
 * Helper class to halt execution on replay (trace collection phase) and to switch thread early on spin-cycles
 */
private class ReplayModeLoopDetectorHelper(
    private val interleavingHistory: List<InterleavingHistoryNode>,
    /**
     * Should we fail with deadlock failure when all events in the current interleaving are completed
     */
    private val failDueToDeadlockInTheEnd: Boolean,
) {

    private var currentInterleavingNodeIndex = 0

    private var executionsPerformedInCurrentThread = 0

    private val currentHistoryNode: InterleavingHistoryNode? get() =
        interleavingHistory.getOrNull(currentInterleavingNodeIndex)

    /**
     * Cycle period if is occurred in during current thread switch or 0 if no spin-cycle happened
     */
    val currentCyclePeriod: Int get() =
        currentHistoryNode?.spinCyclePeriod ?: 0

    /**
     * Returns if we ran in the spin cycle and now are performing executions inside it.
     */
    val currentlyInSpinCycle: Boolean get() =
        currentHistoryNode?.let { it.cycleOccurred && it.executions < executionsPerformedInCurrentThread } ?: false

    fun reset() {
        currentInterleavingNodeIndex = 0
        executionsPerformedInCurrentThread = 0
    }

    /**
     * Called before next execution in current thread.
     */
    @Suppress("UNUSED_PARAMETER") // pass `codeLocation` only for uniformity with `LoopDetector.visitCodeLocation`
    fun visitCodeLocation(codeLocation: Int) {
        executionsPerformedInCurrentThread++
    }

    /**
     * Called before next thread switch
     */
    fun onNextSwitch() {
        currentInterleavingNodeIndex++
        // See threadsRan field description to understand the following initialization logic
        executionsPerformedInCurrentThread = 0
    }

    /**
     * Called to determine if we should switch.
     *
     * @return true if the switch is required, false otherwise.
     */
    fun shouldSwitch(): Boolean {
        return isCurrentHistoryNodeCompleted()
    }

    /**
     * Checks if the current history node is completed.
     * A history node is considered completed if the number of executions performed
     * in the current thread exceeds the sum of the spin cycle period and the executions
     * specified in the current history node.
     *
     * @return true if the current history node is completed, false otherwise.
     */
    private fun isCurrentHistoryNodeCompleted(): Boolean {
        val historyNode = currentHistoryNode ?: return false
        return (executionsPerformedInCurrentThread > historyNode.spinCyclePeriod + historyNode.executions)
    }

    fun detectLivelock(): LoopDetector.Decision {
        val cyclePeriod = currentCyclePeriod
        if (!isCurrentHistoryNodeCompleted()) {
            // do not switch until the current node is completed
            return LoopDetector.Decision.Idle
        }
        if (currentInterleavingNodeIndex == interleavingHistory.lastIndex && failDueToDeadlockInTheEnd) {
            // Fail if we ran into cycle,
            // this cycle node is the last node in the replayed interleaving,
            // and we have to fail at the end of the execution
            // traceCollector.newActiveLockDetected(currentThread, cyclePeriod)
            return LoopDetector.Decision.LivelockFailureDetected(cyclePeriod)
        }
        if (cyclePeriod != 0) {
            return LoopDetector.Decision.LivelockThreadSwitch(cyclePeriod)
        }
        return LoopDetector.Decision.Idle
    }
}

/**
 * Calculates the [SpinCycleStartTracePoint] trace point callStackTrace correctly after all trace points
 * related to the spin cycle are collected.
 *
 * # The problem overview
 *
 * [org.jetbrains.kotlinx.lincheck.trace.TraceCollector] collects two types of the [TracePoint]:
 * 1. TracePoints that represents places where potential context switch points could happened.
 * 2. TracePoints, representing regular, non-atomic method calls.
 *
 * This division is important for us, as [LoopDetector] stores execution points sequences of the
 * first type, causing the challenges, described below.
 *
 * When [SpinCycleStartTracePoint] is added initially to the [trace], its callStackTrace, constructed via
 * `callStackTrace[currentThread]` may be inaccurate. Consider the following example:
 * We have the following code:
 * ```kotlin
 * @Operation
 * fun actor() {
 *     atomicInteger.set(false) // code location = 1
 *     spinLock() // method call code location = 2
 * }
 *
 * fun spinLock() {
 *     while (true) {
 *         val value = getValue() // method call code location = 3
 *         atomicInteger.compareAndSet(value, !value) // code location = 5
 *     }
 * }
 *
 * fun getValue() = atomicInteger.get() // code location = 4
 * ```
 * When we ran into a cycle, we'll have the following code locations history:
 * ```
 * [1, 2, 3, 4, 5, 3, 4, 5, 3, 4 ,5 ..., 3, 4, 5]
 * ```
 * Cycle period here is 3: `[3, 4, 5]` and only two `[1, 2]` executions happened before the cycle.
 * Then, suppose we have a scenario with two actors.
 * The interleaving we have:
 * ```
 * [
 *  1. Execute 2 instructions (switch positions) in thread 1,
 *  2. Execute 1 instruction (switch positions) in the thread 1,
 *  3. Execute 3 instructions (switch positions) in the thread 1 -> execution hung.
 * ]
 * ```
 * It's worth noting that the LoopDetector operates with a switch positions when replaying the
 * execution to collect trace.
 *
 * Due to the internals of the [LoopDetector], [LoopDetector.replayModeCurrentlyInSpinCycle] will only
 * return `true` at the beginning of step 3 described above, as execution only contains a sequence of
 * executed potential switch points, while method call isn't a potential switch point.
 * But at the beginning of step 3 we'll be inside the `getValue` method, so when [LoopDetector.replayModeCurrentlyInSpinCycle]
 * is triggered, it's not correct using `callStackTrace[currentThread]`, as it would contain `getValue`.
 *
 * Summarizing, we may receive the signal about spin cycle start some non-atomic method calls after the actual spin cycle start
 * if we switch right before the first spin cycle potential switch point execution,
 * and this happens as [LoopDetector] stores sequences of the only potential switch points executions and
 * all enters to the non-atomic methods are considered as a part of a step 1, which doesn't correspond to a spin cycle.
 *
 * Hence, **we can only use trace points of the first type defined above (which are potential switch points)
 * to calculate the correct spin cycle start label call depth**.
 *
 * The problem has two solutions, depending on the spin cycle type:
 * * recursive
 * * iterative.
 *
 * # Iterative spin lock
 * Let's consider the solution for the iterative spin-cycle.
 *
 * When we report an iterative spin cycle, we **must** visit the first spin cycle execution point
 * and the first execution point of the second iteration (with an exit before).
 * Let's track the current stacktrace before each switch point, before and after each method calls.
 * Consider the example of a spin cycle, representing call stack traces of the execution points:
 * ```
 * A -> B -> C
 * A -> B -> C -> K
 * A -> B -> E -> D
 * A -> B -> E
 * A -> B -> X
 * ```
 * As we can see, even if all the execution points are wrapped in the non-atomic method calls (which we track
 * during the trace collection too), the longest common prefix of the method calls `A, B` in the stack traces
 * is the right position to place spin cycle start label.
 * Indeed, due to the iterative nature of the spin lock, the first spin cycle execution of the first iteration
 * and of the second iteration are placed in the same depth of calls. So it's guaranteed that we'll visit
 * the most nested call and the least nested call. The wanted recursive method (and its call depth) can be found
 * using the longest prefix of all the points is the spin cycle, as it is going to be the same along all the
 * trace points and method calls.
 *
 * So that's what we do in case of an iterative spin lock.
 * Track all the trace points of the spin cycle,
 * calculate the max common method call prefix of these trace points, and place the spin cycle start label
 * onto the found call depth.
 *
 * # Recursive spin lock
 *
 * Unlike iterative spin lock, in case of a recursive spin lock, longest common prefix may include
 * method calls, that are a part of a spin cycle. Consider the following example:
 * ```kotlin
 * fun actor() {
 *     a()
 * }
 *
 * fun a() = b()
 *
 * fun b() {
 *     c()
 *     c()
 *     a() // recursive call
 * }
 *
 * fun c() = value.get()
 * ```
 * According to the problem described above, if we switch to another thread and back right before point X,
 * the trace points of the spin cycle will have the following stack traces:
 * ```
 * [
 *     actor -> a -> b -> c
 *     actor -> a -> b -> c
 * ]
 * ```
 * And the first execution point of the second iteration will be
 * ```
 * actor -> a -> b -> a -> b -> c
 * ```
 *
 * As mentioned, it's incorrect to say that spin cycle starts at the depth `actor -> a -> c`, as the first
 * recursive call is method `b` call, so we can't use the approach for the iterative spin cycle type.
 *
 * Let's consider the last potential switch trace point before the first spin cycle trace point,
 * the first iteration first potential switch trace point
 * and the second iteration first potential switch trace point:
 *
 * 1. `actor -> a -> b -> c`
 * 2. `actor -> a -> b -> c -> a -> b -> c`
 *
 * Due to the recursive nature of a spin cycle, the second and the third trace points must have common
 * method call suffix.
 * It's important how to compare method calls in the suffixes. We consider method calls identical if
 * they have the same ids produced by [methodCache] and the same parameters. That means we don't care
 * here where this method is called - it's more convenient to see as short version of the spin cycle as possible.
 *
 * But this approach may produce a wrong result in case when we switch from the spin lock and then occur
 * in the same spin lock again.
 * Let's consider this situation using the example above.
 * Trace points of the second spin lock would have the following call stacks:
 *
 * 1. `actor -> [a -> b -> c] -> [a -> b -> c]`
 * 2. `actor -> [a -> b -> c] -> [a -> b -> c]`
 *
 * And the first execution point of the second iteration will be
 * ```
 *     actor -> [a -> b -> c] -> [a -> b -> c] -> [a -> b -> c]
 * ```
 *
 * If we apply this algorithm to the first point from the first iteration and the first point from the second iteration
 * we get `[a -> b -> c] -> [a -> b -> c]` longest common suffix, which is not correct, because the first recursive call
 * of this cycle starts at the depth `actor -> a -> b`.
 * In this case, the last trace point before the spin cycle becomes handy.
 * In the example above it would have the following call stack `actor -> a -> b -> c`.
 *
 * Here are the points we're interested in:
 * 1. `actor -> [a -> b -> c]` - The last trace point before the cycle.
 * 2. `actor -> [a -> b -> c] -> [a -> b -> c]` - The first trace point of the cycle.
 * 3. ` actor -> [a -> b -> c] -> [a -> b -> c] -> [a -> b -> c]` - The first trace point of the second iteration.
 * Let's note the following rule: if point 1 has the same method call on the same depth as point 2,
 * then this call can't be a part of the current spin cycle.
 * The reason is quite easy: if it was, we would mark point 1 as a first spin cycle trace point.
 *
 * So, to detect the spin cycle, start trace point depth in case of a recursive spin lock we:
 * 1. Take the first trace point of the spin cycle on the first iteration (point A) and on the second iteration (point B).
 * 2. Take the last trace point before the spin cycle (point C).
 * 3. We walk synchronously on their call stacks from the end to the beginning, while call from the A stack
 * is the same as a call from the stack B. But it also equals the call from the call C, then we need to stop.
 * The count of the call passed the condition above equals to the call we need to lift from the first spin cycle
 * node to get the correct spin cycle start trace point depth.
 */
internal fun recomputeSpinCycleStartCallStack(
    spinCycleStartTracePoint: TracePoint,
    spinCycleEndTracePoint: TracePoint,
) : List<MethodCallTracePoint> {
    check(spinCycleStartTracePoint is SpinCycleStartTracePoint)
    check(spinCycleEndTracePoint is SwitchEventTracePoint ||
          spinCycleEndTracePoint is ObstructionFreedomViolationExecutionAbortTracePoint)

    val spinCycleFirstTracePointCallStackTrace = spinCycleStartTracePoint.callStackTrace.map { it.tracePoint }
    val spinCycleLastTracePointCallStackTrace = when (spinCycleEndTracePoint) {
        is SwitchEventTracePoint -> spinCycleEndTracePoint.callStackTrace.map { it.tracePoint }
        is ObstructionFreedomViolationExecutionAbortTracePoint -> spinCycleEndTracePoint.callStackTrace.map { it.tracePoint }
        else -> error("Unreachable code")
    }

    val isRecursive = (spinCycleLastTracePointCallStackTrace.size != spinCycleFirstTracePointCallStackTrace.size)
    return if (isRecursive) {
        getCommonRecursiveStackTrace(spinCycleFirstTracePointCallStackTrace, spinCycleLastTracePointCallStackTrace)
    } else {
        getCommonMinStackTrace(listOf(spinCycleFirstTracePointCallStackTrace, spinCycleLastTracePointCallStackTrace))
    }
}

/**
 * @return Max common prefix of the [StackTraceElement] of the provided [spinCycleCallStacks].
 */
private fun getCommonMinStackTrace(spinCycleCallStacks: List<List<MethodCallTracePoint>>): List<MethodCallTracePoint> {
    var count = 0
    outer@while (count < spinCycleCallStacks[0].size) {
        val stackTraceElement = spinCycleCallStacks[0][count]
        for (i in 1 until spinCycleCallStacks.size) {
            val traceElements = spinCycleCallStacks[i]
            if (count == traceElements.size) break@outer
            if (stackTraceElement !== traceElements[count]) break@outer
        }
        count++
    }
    return spinCycleCallStacks.first().take(count)
}

private fun getCommonRecursiveStackTrace(
    first: List<MethodCallTracePoint>,
    last: List<MethodCallTracePoint>
): List<MethodCallTracePoint> {
    var i = first.lastIndex
    var j = last.lastIndex
    var count = 0
    while (i >= 0 && j >= 0) {
        if (!first[i].isEqualInvocation(last[j])) break

        i--
        j--
        count++
    }
    return first.dropLast(count)
}

private fun MethodCallTracePoint.isEqualInvocation(other: MethodCallTracePoint): Boolean =
    this.className == other.className &&
    this.methodName == other.methodName &&
    this.parameters?.size == other.parameters?.size &&
    this.parameters == other.parameters